package 热题100.二叉树.翻转二叉树_226_简单;
import 热题100.二叉树.二叉树的中序遍历_94_简单.Solution.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/*
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

思路：
    利用层序遍历，在原来加入节点的地方换成交换左右节点
* */
public class Solution {
    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node3, null);
        TreeNode root = new TreeNode(1, null, node2);
        TreeNode ans = invertTree(root);
    }
    public static TreeNode invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        // 队列先进先出
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.offer(root);
        while (!stack.isEmpty()){
            // 记录当前层的大小
            int len = stack.size();
            while (len -- > 0){
                // 拿出当前节点，然后翻转它的左右节点
                TreeNode cur = stack.poll();
                swap(cur);
                // 继续加入到队列，相当于下一层
                if (cur.right != null) {
                    stack.offer(cur.right);
                }
                if (cur.left != null){
                    stack.offer(cur.left);
                }
            }
        }
        return root;
    }

    public static void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
